#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
private:
    vector<int>manacher(const string& str) {
        string s(str.length() * 2 + 3, '#');
        s[0] = '$'; s.back() = '^';
        for (int i = 0; i < str.length(); ++i)
            s[2 * i + 2] = str[i];
        vector<int>dp(s.length(), 1);
        dp[0] = -1;
        int c = 0;
        for (int i = 1; i < s.length(); ++i) {
            if (i < c + dp[c])
                dp[i] = min(dp[2 * c - i], c + dp[c] - i);
            int left = i - dp[i];
            int right = i + dp[i];
            while (s[left] == s[right]) {
                --left;
                ++right;
                ++dp[i];
            }
            if (c + dp[c] < i + dp[i])
                c = i;
        }
        return dp;
    }
    bool isPalindrome(const vector<int>& cdp, int start, int end) {
        start = 2 * start + 1;
        end = 2 * end + 2;
        int center = (start + end) / 2;
        return cdp[center] >= end - center;
    }
public:
    int minCut(string s) {
        if (s.length() < 2) return 0;
        auto cdp = manacher(s);
        vector<int>dp(s.length()+1, s.length());
        dp[0] = -1;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (isPalindrome(cdp, j, i)) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp.back();
    }
};

int main() {
    Solution sol;
    sol.minCut("cbbbcc");
}